一、EGES [2018]

《Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba》

1. 互联网技术不断重塑商业格局，如今电商无处不在。阿里巴巴是中国最大的电商平台，它使得全世界各地的个人或公司都可以在线开展业务。阿里巴巴拥有 10 亿用户，2017 年的商品交易总额（Gross Merchandise Volume: GMV）为 37670 亿元，2017 年的收入为 1580 亿元。在著名的 “双十一” 这个中国最大的网络购物节，2017 年的GMV 约为 1680 亿元。在阿里巴巴的各类在线平台中，最大的在线 consumer-to-consumer: C2C 平台淘宝贡献了阿里巴巴电商总流量的 75% 。

   淘宝拥有10 亿用户和 20 亿item （即商品），最关键的问题是如何帮助用户快速找到需要的、感兴趣的item 。为了实现这一目标，基于用户偏好（preference）从而为用户提供感兴趣的 item 的推荐技术成为淘宝的关键技术。例如，手机淘宝首页（如下图所示）是根据用户历史行为而通过推荐技术生成的，贡献了总推荐流量的 40%。此外，推荐贡献了淘宝的大部分收入和流量。总之，推荐已经成为淘宝和阿里巴巴的 GMV 和收入的重要引擎。下图中，用虚线矩形框突出显示的区域是针对淘宝上十亿用户的个性化。为了更好的用户体验（user experience），我们还生成了吸引人的图像和文本描述。

   

   尽管学术界和工业界的各种推荐方法取得了成功，例如协同过滤（collaborative filtering: CF）、基于内容的方法、基于深度学习的方法，但是由于用户和item 的十亿级的规模，这些方法在淘宝上面临的问题变得更加严重。推荐系统在淘宝面临三大技术挑战：

   • 可扩展性（scalability）：尽管很多现有的推荐方法在较小规模的数据集（即数百万用户和 item）上运行良好，但是在淘宝的、大得多的数据集（即10 亿用户和 20 亿 item）上无法运行。

   • 稀疏性（sparsity）：由于用户往往只与少量 item 进行交互，因此很难训练出准确的推荐模型，尤其是对于交互次数很少的用户或 item。这通常被称作稀疏性问题。

   • 冷启动（cold start）：在淘宝，每小时都有数百万新的 item 不断上传。这些 item 没有用户行为。处理这些 item 或预测用户对这些 item 的偏好具有挑战性，这就是所谓的冷启动问题。

     稀疏性和冷启动都是因为数据太少导致的，冷启动是完全没有历史交互，而稀疏性是只有很少的历史交互。

   为了解决淘宝的这些挑战，我们在淘宝的技术平台中设计了一个两阶段的推荐框架。第一阶段是 matching，第二阶段是 ranking。

   • 在 matching 阶段，我们为每个用户，根据该用户的历史交互的每个 item 生成相似 item 的候选集合（candidate set）。

   • 在 ranking 阶段，我们训练一个深度神经网络模型，该模型根据每个用户的偏好对候选 item 进行排序。

   由于上述挑战，在这两个阶段我们都必须面对不同的独特问题（different unique problems）。此外，每个阶段的目标不同，导致技术解决方案也不同。在论文 《Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba》 中，我们专注于如何解决 matching 阶段的挑战，其中核心任务是根据用户的行为计算所有 item 之间的 pairwise 相似性（similarity）。在获得 item 的 pairwise 相似性之后，我们可以生成候选 item 的集合，以便在 ranking 阶段进一步个性化。

   为了实现这一点，我们提出从用户的行为历史构建一个 item graph，然后应用 SOTA 的 graph embedding 方法来学习每个 item 的 embedding，我们称之为Base Graph Embedding: BGE 。通过这种方式，我们可以根据从 item embedding 向量的内积计算出的相似性来生成候选 item 集合。注意，以前的工作使用 CF-based 方法来计算 item 之间的相似性，而CF-based 方法仅考虑用户行为历史中 item 的共现（co-occurrence）。但是在我们的工作中，通过在 item graph 中使用随机游走，我们可以捕获 item 之间的高阶相似性。因此，我们的方法优于 CF-based 方法。

   然而，在很少交互、甚至没有交互的情况下学习 item 的精确embedding 仍然是一个挑战。为了缓解这个问题，我们提出使用辅助信息（side information）来提升（enhance） embedding 过程，我们称之为 Graph Embedding with Side information: GES。例如，属于同一类目（category）或同一品牌（brand）的 item 在 embedding 空间中应该更接近。通过这种方式，我们可以在很少交互甚至没有交互的情况下获得 item 的精确 embedding 。

   然而，在淘宝中有数百种类型的辅助信息，如类目、品牌、价格等等。直观而言，不同的辅助信息对学习 item 的 embedding 应该有不同的贡献。因此，我们进一步提出了一种在学习带辅助信息的 embedding 时的加权机制，称作 Enhanced Graph Embedding with Side information: EGES 。

   本文主要贡献：

   • 基于淘宝多年的实践经验，我们设计了一种有效的启发式（heuristic）方法，从淘宝上十亿用户的行为历史构建 item graph 。

   • 我们提出了三种 embedding 方法（BGE、GES、EGES ）来学习淘宝中 20 亿 item 的 embedding。我们进行离线实验以证明 BGE、GES、EGES 和其它 embedding 方法相比的有效性。

   • 为了在淘宝中为十亿级用户和 item 部署所提出的方法，我们在我们团队搭建的 XTensorflow: XTF 平台上构建了 graph embedding system。我们表明，所提出的框架显著提高了手机淘宝App 的推荐性能，同时满足了双十一当天训练效率和 serving 的即时响应（instant response）的需求。

2. 相关工作：这里我们简要回顾 graph embedding、带辅助信息的 graph embedding、以及用于推荐的 graph embedding 的相关工作。

   • Graph Embedding：graph embedding 算法已经作为一种通用的网络表示方法，它们已被用于很多实际 application。在过去的几年里，该领域有很多研究专注于设计新的 embedding 方法。这些方法可以分为三类：

     • LINE 等分解方法尝试近似分解邻接矩阵并保留一阶和二阶邻近性。

     • 深度学习方法增强（enhance）了模型捕获图中非线性的能力。

     • 基于随机游走的技术在图上使用随机游走来获得非常有效的node representation ，因此可用于超大规模网络。

     在本文中，我们的 embedding 框架基于随机游走。

   • 带辅助信息的 Graph Embedding：上述 graph embedding 方法仅使用网络的拓扑结构，存在稀疏性和冷启动的问题。近年来，很多工作试图结合辅助信息来增强 graph embedding 方法。大多数工作基于具有相似辅助信息的节点在 embedding 空间中应该更接近的假设来构建他们的任务。为了实现这一点，《Discriminative deep random walk for network classification》 和 《Max-margin deepwalk: Discriminative learning of network representation》 提出了一个联合框架来优化带分类器函数的 embedding 目标函数。论文 《Representation learning of knowledge graphs with hierarchical types 》 进一步将复杂的知识图谱嵌入到具有层级结构（hierarchical structure）（如子类目）的节点中。

     此外，也有一部分工作将节点相关的文本信息融合到 graph embedding 中。另外， 《Heterogeneous network embedding via deep architectures》 提出了一个深度学习框架来为异质 graph embedding 同时处理文本和图像特征。

     在本文中，我们主要处理淘宝中item 相关的离散辅助信息，例如类目（category）、品牌（brand）、价格等，并在 embedding 框架中设计了一个 hidden layer 来聚合不同类型的辅助信息。

   • 用于推荐的 Graph Embedding：推荐一直是 graph embedding 最流行的下游任务之一。有了 node representation，就可以使用各种预测模型进行推荐。

     在 《Personalized entity recommendation: A heterogeneous information network approach》 和 《Meta-graph based recommendation fusion over heterogeneous information networks》 中，user embedding 和 item embedding 分别在 meta-path 和 meta-graph 的监督下在异质信息网络（heterogeneous information network）中学习。

     • 《Personalized entity recommendation: A heterogeneous information network approach》 为推荐任务提出了一个线性模型来聚合 embedding。

     • 《Meta-graph based recommendation fusion over heterogeneous information networks》 提出将分解机（factorization machine: FM ）应用于embedding 以进行推荐。

     《Collaborative knowledge base embedding for recommender systems》 提出了一个联合 embedding 框架，从而为推荐任务学习 graph, text, image 的 embedding。《Scalable graph embedding for asymmetric proximity》 提出了 graph embedding 来捕获节点推荐（node recommendation）的非对称相似性（asymmetric similarity）。

     在本文中，我们的 graph embedding 方法被集成到一个两阶段推荐平台中。因此，embedding 的性能将直接影响最终的推荐结果。

1.1 模型

1. 我们首先介绍 graph embedding 的基础知识，然后详细说明我们如何根据用户的行为历史来构建 item graph，最后我们研究了在淘宝中学习 item embedding 的方法。

2. Graph Embedding：这里我们概述了 graph embedding，以及最流行的一种 graph embedding 方法 ：DeepWalk。我们是在 DeepWalk 的基础上提出了 matching 阶段的 graph embedding 方法。

   给定一个图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G = (\mathcal V, \mathcal E)$，其中 $\mathcal{V}$$\mathcal V$ 代表节点集合、$\mathcal{E}$$\mathcal E$ 代表边集合。graph embedding 是为每个节点 $v\in \mathcal{V}$$v\in \mathcal V$ 在低维空间 ${\mathbb{R}}^d$$\mathbb R^d$ 中学习一个低维representation ，其中 $d\ll |\mathcal{V}|$$d\ll |\mathcal V|$ 。换句话讲，我们的目标是学习一个映射函数 $\mathrm{\Phi }:\mathcal{V}\to {\mathbb{R}}^d$$\Phi:\mathcal V\rightarrow \mathbb R^d$ ，即把 $\mathcal{V}$$\mathcal V$ 中的每个节点表示为一个 $d$$d$ 维的向量。

   受到 word2vec 的启发，Perozzi 等人提出了 DeepWalk 来学习图中每个节点的 embedding。他们首先通过在图中运行随机游走来生成节点序列，然后应用 Skip-Gram 算法来学习图中每个节点的 representation。为了保持图的拓扑结构，他们需要解决以下最优化问题：

   $$\underset{\mathrm{\Phi }}{min}\sum _{v\in \mathcal{V}}\sum _{c\in \mathcal{N}(v)}-\log p(c\mid \mathrm{\Phi }(v))$$

   其中：

   • $\mathcal{N}(v)$$\mathcal N(v)$ 为节点 $v$$v$ 的邻居节点集合，它可以定义为节点 $v$$v$ 的 1-hop 或者 2-hop 节点集合。

   • $p(c\mid \mathrm{\Phi }(v))$$p(c\mid \Phi(v))$ 定义了在给定节点 $v$$v$ 的情况下，拥有上下文节点 $c$$c$ 的条件概率。

   接下来，我们首先介绍如何根据用户的历史行为构建 item graph，然后提出基于 DeepWalk 的 graph embedding 方法，从而为淘宝中的 20 亿 item 生成低维 representation。

3. 构建 Item Graph：这里，我们将详细说明从用户历史行为构建 item graph。

   实际上，用户在淘宝上的行为往往是连续的，如图 (a) 所示。以往的 CF-based 方法仅考虑 item 的共现（co-occurrence），而忽略了可以更准确地反映用户偏好的序列信息（sequential information ）。 然而，不可能使用用户的全部历史记录（来作为一个序列），有两个原因：

   • 条目（ entry ）太多，导致计算成本和空间成本太高。

   • 用户的兴趣会随着时间而漂移（drift）。

   因此在实践中，我们设置了一个时间窗口，仅选择用户在窗口内的行为。这称为 session-based 用户行为。根据经验，时间窗口的大小为一个小时。例如图 (a) 中，包含用户 $u_1$$u_1$ 的一个 session、用户 $u_2$$u_2$ 的两个 session、用户 $u_3$$u_3$ 的两个session。

   在我们获得 session-based 用户行为之后，如果两个 item 相连地（consecutively）出现，则它们通过有向边连接。如下图 (b) 所示：item D 和 item A 相连，因为用户 $u_1$$u_1$ 先后陆续访问了 item D 和 item A。

   这种图构建方式捕获了序列关系。如果是连接 session 内的任意两个item，则捕获了共现关系。

   利用淘宝上所有用户的协同行为（collaborative behaviors），我们根据所有用户行为中两个相连 item 的出现总数为每条边 $e_{i,j}$$e_{i,j}$ 分配一个权重。具体而言，边 $e_{i,j}$$e_{i,j}$ 的权重等于所有用户行为历史中 item $i$$i$ 转移到 item $j$$j$ 的频次。通过这种方式，构建的 item graph 可以基于淘宝中所有用户的行为来表示不同 item 之间的相似性。图 (b) 为根据图 $(a)$$(a)$ 得到的加权有向图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$ 。

   

   在实践中，我们在抽取用户行为序列之前需要过滤掉无效数据（invalid data）和异常行为（abnormal behaviors），从而消除噪声。目前，以下行为在我们的系统中被视为噪声：

   • 如果点击之后停留的时间少于一秒钟，那么点击可能是无意的，则需要移除。

   • 淘宝上有一些 “过度活跃” 的用户，他们实际上是作弊用户（spam users）。根据我们在淘宝上的长期观察，如果单个用户在不到三个月内，总购买数量大于 1000 或者总点击数量大于 3500，则该用户很可能是作弊用户。我们需要过滤掉这些用户的行为。

   • 淘宝的零售商不断地更新商品的详细信息。在极端情况下，一个商品在经过长时间的更新之后，在淘宝上可能变成完全不同的商品，即使它们具有相同的商品id。因此，我们删除了这些 id 相关的 item（即更新前后，该id 代表了完全不同的商品）。

4. Base Graph Embedding: BGE：在得到有向加权图（记作 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E )$）之后，我们采用 DeepWalk 来学习每个节点在 $\mathcal{G}$$\mathcal G$ 中的 embedding。

   令 $\mathbf{M}$$\mathbf M$ 表示 $\mathcal{G}$$\mathcal G$ 的邻接矩阵，$M_{i,j}$$M_{i,j}$ 表示从节点 $i$$i$ 指向节点 $j$$j$ 的边的权重。我们首先基于随机游走生成节点序列，然后对节点序列运行 Skip-Gram 算法。随机游走的转移概率定义为：

   $$\begin{array}{c}p(v_j\mid v_i)=\{\begin{array}{ll}\frac{M_{i,j}}{\sum _{j^{\prime }\in {\mathcal{N}}_{+}(v_i)}{M}_{i,j^{\prime }}}& ,v_j\in {\mathcal{N}}_{+}(v_i)\\ 0& ,\text{else}\end{array}\end{array}$$

   其中 ${\mathcal{N}}_{+}(v_i)$$\mathcal N_+(v_i)$ 为 outlink 邻居的集合，即 $v_i$$v_i$ 的出边 （outedge）指向的节点集合。

   通过运行随机游走，我们可以生成许多序列，如下图 (c) 所示。然后我们应用 Skip-Gram 算法（如图 (d) 所示）来学习节点 embedding，从而最大化随机游走序列中两个节点的共现概率（occurrence probability）。这导致了以下的最优化问题：

   $$\underset{\mathrm{\Phi }}{min}-\log p(\{v_{i-K},\cdots ,v_{i-1},v_{i+1},\cdots ,v_{i+K}\}\mid \mathrm{\Phi }(v_i))$$

   其中 $K$$K$ 是随机游走序列中上下文节点的窗口大小。

   使用独立性假设，我们有：

   $$p(\{v_{i-K},\cdots ,v_{i-1},v_{i+1},\cdots ,v_{i+K}\}\mid \mathrm{\Phi }(v_i))=\prod _{j=i-K,j\ne i}^{i+K}p(v_j\mid \mathrm{\Phi }(v_i))$$

   其中：

   $$p(v_j\mid \mathrm{\Phi }(v_i))=\frac{\exp (\mathrm{\Phi }(v_j{)}^{\mathrm{\top }}\mathrm{\Phi }(v_i))}{\sum _{j^{\prime }\in \mathcal{V}}\exp (\mathrm{\Phi }(v_{j^{\prime }}{)}^{\mathrm{\top }}\mathrm{\Phi }(v_i))}$$

   应用负采样技术，则最优化问题可以转化为：

   $$\underset{\mathrm{\Phi }}{min}\log \sigma (\mathrm{\Phi }(v_j{)}^{\mathrm{\top }}\mathrm{\Phi }(v_i))+\sum _{t\in \mathcal{S}(v_i)}\log \sigma (-\mathrm{\Phi }(v_t{)}^{\mathrm{\top }}\mathrm{\Phi }(v_i))$$

   其中： $\mathcal{S}(v_i)$$\mathcal S(v_i)$ 表示节点 $v_i$$v_i$ 的负样本集合， $\sigma (\cdot )$$\sigma(\cdot)$ 为 sigmoid 函数。根据经验，负样本规模越大则最终结果越好。

   

5. Graph Embedding with Side information: GES：通过应用上述 embedding 方法，我们可以学习淘宝中所有item 的 embedding，从而捕获用户行为序列中的高阶相似性。而这种高阶相似性在以前的 CF-based 方法中被忽略。然而，学习 “冷启动” item （即那些没有用户交互的 item）的accurate embedding 仍然具有挑战性。

   为了解决冷启动问题，我们提出使用附加到冷启动item 的辅助信息（side information）来增强（enhance） BGE。在电商推荐系统的上下文中，辅助信息指的是item 的类目（category）、门店（shop）、价格（price）等信息，这些信息在ranking 阶段被广泛用作关键特征，但是在matching 阶段很少使用。我们可以通过在 graph embedding 中融合辅助信息来缓解冷启动问题。例如，优衣库（相同门店）的两件帽衫（相同类目）可能看起来很像；喜欢尼康镜头的用户也可能对佳能相机（相似类目、相似品牌）感兴趣。这意味着具有相似辅助信息的 item 应该在 embedding 空间中更接近。基于这个假设，我们提出了如下图所示的 GES 方法。

   我们使用 $\mathbf{E}$$\mathbf E$ 来表示 item 或辅助信息的 embedding 矩阵，具体而言：

   • ${\mathbf{E}}^0\in {\mathbb{R}}^{|\mathcal{V}|\times d}$$\mathbf E ^0\in \mathbb R^{|\mathcal V|\times d}$ 表示item embedding 矩阵。

   • ${\mathbf{E}}^f\in {\mathbb{R}}^{|\mathcal{V}|\times d},1\le f\le F$$\mathbf E^f\in \mathbb R^{|\mathcal V|\times d},1\le f\le F$ 表示第 $f$$f$ 种类型辅助信息的 embedding 矩阵，一共有 $F$$F$ 种类型的辅助信息。

   其中 $d$$d$ 为 embedding 维度。注意，item embedding 维度和辅助信息 embedding 维度都设为相同的值。

   为了融合辅助信息，我们将item $v$$v$ 的 $F+1$$F+1$ 个 embedding 向量拼接起来，并用均值池化来来聚合item $v$$v$ 相关的所有 embedding，即：

   $${\overrightarrow{\mathbf{h}}}_v=\frac{1}{F+1}\sum _{f=0}^F{\overrightarrow{\mathbf{e}}}_v^f$$

   其中： ${\overrightarrow{\mathbf{h}}}_v$$\mathbf{\vec h}_v$ 为item $v$$v$ 聚合后的 embedding； ${\overrightarrow{\mathbf{e}}}_v^f$$\mathbf{\vec e}_v^f$ 为 ${\mathbf{E}}^f$$\mathbf E^f$ 的第 $v$$v$ 行，表示item $v$$v$ 的 item embedding 向量或者第 $f$$f$ 类辅助信息的 embedding 向量。所有节点聚合后的 embedding 构成了embedding 矩阵 $\mathbf{H}$$\mathbf H$ 。

   ${\mathbf{E}}^0$$\mathbf E^0$ 是 graph embedding 矩阵，它是通过 DeepWalk 算法得到。但是这里辅助信息 embedding 矩阵 ${\mathbf{E}}^f$$\mathbf E^f$ 如何得到？论文并未给出明确的回答。

   通过这种方式，我们融合了辅助信息，使得具有相似辅助信息的item 在 embedding 空间中更为接近。这使得冷启动 item 的 embedding 更为准确（accurate），并提高了离线和在线性能。

   下图为GES 和 EGES 的总体架构。SI 表示辅助信息（side information），SI 0 表示 item 本身。

   • Sparse Features 往往是 item ID 以及不同 SI 的one-hot 向量。

   • Dense Embeddings 是 item 和相应 SI 的 representation 。

   • Hidden Representation 是一个 item 及其相应 SI 的embedding 聚合结果。

   

6. Enhanced Graph Embedding with Side information: EGES：尽管 GES 的性能有所提升，但是在 embedding 过程中融合不同类型的辅助信息时仍然存在问题。在 GES 中，我们假设不同类型的辅助信息对于最终 embedding 的贡献相等，这不符合现实。例如：购买了 iPhone 的用户会因为 Apple 这个品牌而倾向于查看 Macbook 或 iPad；用户可能在同一家门店购买不同品牌的衣服，因为比较方便（convenience）而且价格更低（因为可能存在折扣）。因此，不同类型的辅助信息对用户行为中 item 共现（co-occurrence）的贡献不同。

   为了解决这个问题，我们提出了 EGES 方法来聚合不同类型的辅助信息。EGES 框架和 GES 相同，它的基本思想是：不同类型的辅助信息在它们的 embedding 被聚合时有不同的贡献。因此，我们提出一个加权均值池化层来聚合辅助信息的 embedding 。

   定义一个加权的权重矩阵 $\mathbf{A}\in {\mathbb{R}}^{|\mathcal{V}|\times (F+1)}$$\mathbf A\in \mathbb R^{|\mathcal V|\times (F+1)}$，其中 $A_{i,j}$$A_{i,j}$ 表示在第 $i$$i$ 个 item 中，第 $j$$j$ 种类型辅助信息的加权系数。

   • $A[:,0]$$A[:,0]$ （即 $\mathbf{A}$$\mathbf A$ 的第一列）表示item embedding 自己的权重。$A[v,0]$$A[v,0]$ 表示 item $v$$v$ 的 item embedding 权重。

   • $A[:,f],1\le f\le F$$A[:,f], 1\le f\le F$ （即 $\mathbf{A}$$\mathbf A$ 的第 $f$$f$ 列）表示第 $f$$f$ 种辅助信息的权重。$A[v,f]$$A[v,f]$ 表示 item $v$$v$ 的第 $f$$f$ 种辅助信息的权重。

   注意：这里对不同的节点设置个性化的权重分布，而不是采用统一的权重分布。考虑到 embedding 参数数量为 $|\mathcal{V}|\times d\times (F+1)$$|\mathcal V|\times d\times (F+1)$，因此权重矩阵的参数规模是 embedding 参数的 $1/d$$1/d$ 。

   那么加权均值聚合的结果为：

   $${\overrightarrow{\mathbf{h}}}_v=\frac{\sum _{f=0}^F\exp (A[v,f]){\overrightarrow{\mathbf{e}}}_v^f}{\sum _{f=0}^F\exp (A[v,f])}$$

   这里我们使用 $\exp (\cdot )$$\exp(\cdot)$ 函数的原因是为了确保辅助信息的权重大于零。

   给定节点 $v$$v$ 以及上下文节点 $c$$c$ ，令 ${\overrightarrow{\mathbf{z}}}_c\in {\mathbb{R}}^d$$\mathbf{\vec z}_c\in \mathbb R^d$ 为上下文节点 $c$$c$ 的 embedding。令 $y\in \{0,1\}$$y\in \{0,1\}$ 为 label（如是否点击），则 EGES 的目标函数为：

   $$\mathcal{L}(v,c,y)=-[y\log \left(\sigma \left({\overrightarrow{\mathbf{h}}}_v^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_c\right)\right)+(1-y)\log (1-\sigma \left({\overrightarrow{\mathbf{h}}}_v^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_c\right))]$$

   我们基于梯度下降法来求解最优化问题，其梯度为：

   $${\mathrm{\nabla }}_{{\overrightarrow{\mathbf{z}}}_c}\mathcal{L}=(\sigma \left({\overrightarrow{\mathbf{h}}}_v^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_c\right)-y){\overrightarrow{\mathbf{h}}}_v$$
   $$\begin{array}{c}\frac{\partial \mathcal{L}}{\partial A[v,f]}=\frac{\partial \mathcal{L}}{\partial {\overrightarrow{\mathbf{h}}}_v}\frac{\partial {\overrightarrow{\mathbf{h}}}_v}{\partial A[v,f]}\\ =(\sigma \left({\overrightarrow{\mathbf{h}}}_v^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_c\right)-y){\overrightarrow{\mathbf{z}}}_c\cdot \frac{(\sum _{f^{\prime }=0}^F\exp (A[v,f^{\prime }]))\exp (A[v,f]){\overrightarrow{\mathbf{e}}}_v^f-\exp (A[v,f])\sum _{f^{\prime }=0}^F\exp (A[v,f^{\prime }]){\overrightarrow{\mathbf{e}}}_v^{f^{\prime }}}{{(\sum _{f^{\prime }=0}^F\exp (A[v,f^{\prime }]))}^2}\end{array}$$
   $${\mathrm{\nabla }}_{{\overrightarrow{\mathbf{e}}}_v^f}\mathcal{L}={\mathrm{\nabla }}_{{\overrightarrow{\mathbf{h}}}_v}\mathcal{L}{\mathrm{\nabla }}_{{\overrightarrow{\mathbf{e}}}_v^f}{\overrightarrow{\mathbf{h}}}_v=\frac{\exp (A[v,f])}{\sum _{f^{\prime }=0}^F\exp (A[v,f^{\prime }])}(\sigma \left({\overrightarrow{\mathbf{h}}}_v^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_c\right)-y){\overrightarrow{\mathbf{z}}}_c$$

   对于冷启动 item，虽然 item embedding ${\overrightarrow{\mathbf{e}}}^0$$\mathbf{\vec e}^0$ 未知，但是辅助信息 embedding ${\overrightarrow{\mathbf{e}}}^f,f>0$$\mathbf{\vec e}^f,f\gt 0$ 可以获取。

7. EGES 框架算法：

   • 输入：

     • 图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$

     • 辅助信息 $\mathcal{S}$$\mathcal S$

     • 每个节点作为起始点的随机游走数量 $N$$N$

     • 随机游走序列长度 $L$$L$

     • Skip-Gram 窗口大小 $K$$K$

     • 负样本数量 $N^{-}$$N^-$

     • embedding 维度 $d$$d$

   • 输出：

     • item embedding 矩阵和辅助信息 embedding 矩阵 ${\mathbf{E}}^0,\cdots ,{\mathbf{E}}^F$$\mathbf E^0,\cdots,\mathbf E^F$ 。

     • 权重矩阵 $\mathbf{A}$$\mathbf A$ 。

   • 算法步骤：

     • 初始化 ${\mathbf{E}}^0,\cdots ,{\mathbf{E}}^F,\mathbf{A}$$\mathbf E^0,\cdots,\mathbf E^F,\mathbf A$ 。

     • 迭代 $i=1,\cdots ,N$$i =1,\cdots,N$ ，迭代步骤为：

       迭代 $v\in \mathcal{V}$$v\in \mathcal V$，迭代步骤为：

       • 通过随机游走得到序列：$\text{SEQ = RandomWalk}(\mathcal{G},v,L)$$\text{SEQ = RandomWalk}(\mathcal G,v,L)$ 。随机游走概率由 $p(v_j\mid v_i)$$p(v_j\mid v_i)$ 决定。

       • 执行加权 SkipGram 算法：$\text{WeightedSkipGram}({\mathbf{E}}^0,\cdots ,{\mathbf{E}}^F,\mathbf{A},K,N^{-},L,\text{SEQ})$$\text{WeightedSkipGram}(\mathbf E^0,\cdots,\mathbf E^F,\mathbf A,K,N^-,L,\text{SEQ})$ 。

     • 返回 ${\mathbf{E}}^0,\cdots ,{\mathbf{E}}^F,\mathbf{A}$$\mathbf E^0,\cdots,\mathbf E^F,\mathbf A$ 。

8. 加权 Skip-Gram 算法：

   • 输入：

     • ${\mathbf{E}}^0,\cdots ,{\mathbf{E}}^K,\mathbf{A}$$\mathbf E^0,\cdots,\mathbf E^K,\mathbf A$ 。

     • Skip-Gram 窗口大小 $K$$K$

     • 负样本数量 $N^{-}$$N^-$

     • 随机游走序列长度 $L$$L$

     • 随机游走序列 SEQ

   • 输出：更新后的 ${\mathbf{E}}^0,\cdots ,{\mathbf{E}}^F,\mathbf{A}$$\mathbf E^0,\cdots,\mathbf E^F,\mathbf A$ 。

   • 算法步骤：

     迭代，$i=1,\cdots ,L$$i=1,\cdots,L$ ，迭代步骤为：

     $v=\text{SEQ}[i]$$v=\text{SEQ}[i]$ 为当前节点。遍历窗口，$v=max(0,i-K),\cdots ,min(i+K,L);j\ne i$$v=\max(0,i-K),\cdots,\min(i+K,L); j\ne i$，迭代步骤为：

     • 正样本梯度更新（label = 1）：

       • $c=\text{SEQ}[j]$$c=\text{SEQ}[j]$

       • 更新 ${\overrightarrow{\mathbf{z}}}_c$$\mathbf{\vec z}_c$： ${\overrightarrow{\mathbf{z}}}_c\leftarrow {\overrightarrow{\mathbf{z}}}_c-\eta \times {\mathrm{\nabla }}_{{\overrightarrow{\mathbf{z}}}_c}\mathcal{L}$$\mathbf{\vec z}_c\leftarrow \mathbf{\vec z}_c-\eta\times \nabla_{\mathbf{\vec z}_c} \mathcal L$ 。

       • 迭代，$f=0,\cdots ,F$$f=0,\cdots,F$，更新：

         $$\begin{array}{c}A[v,f]\leftarrow A[v,f]-\eta \times \frac{\partial \mathcal{L}}{\partial A[v,f]}\\ {\overrightarrow{\mathbf{e}}}_v^f\leftarrow {\overrightarrow{\mathbf{e}}}_v^f-\eta \times {\mathrm{\nabla }}_{{\overrightarrow{\mathbf{e}}}_v^f}\mathcal{L}\end{array}$$

     • 负样本梯度更新（label = 0），$t=0,\cdots ,N^{-}$$t=0,\cdots,N^-$ ，迭代过程为：

       • 从 $\mathcal{V}$$\mathcal V$ 中负采样出顶点 $c$$c$ 。

       • 更新 ${\overrightarrow{\mathbf{z}}}_c$$\mathbf{\vec z}_c$： ${\overrightarrow{\mathbf{z}}}_c\leftarrow {\overrightarrow{\mathbf{z}}}_c-\eta \times {\mathrm{\nabla }}_{{\overrightarrow{\mathbf{z}}}_c}\mathcal{L}$$\mathbf{\vec z}_c\leftarrow \mathbf{\vec z}_c-\eta\times \nabla_{\mathbf{\vec z}_c} \mathcal L$ 。

       • 迭代，$f=0,\cdots ,F$$f=0,\cdots,F$，更新：

         $$\begin{array}{c}A[v,f]\leftarrow A[v,f]-\eta \times \frac{\partial \mathcal{L}}{\partial A[v,f]}\\ {\overrightarrow{\mathbf{e}}}_v^f\leftarrow {\overrightarrow{\mathbf{e}}}_v^f-\eta \times {\mathrm{\nabla }}_{{\overrightarrow{\mathbf{e}}}_v^f}\mathcal{L}\end{array}$$

    

9. 未来方向：

   • 首先是在 graph embedding 方法中利用 attention 机制，这可以提供更大的灵活性来学习不同类型辅助信息的权重。

   • 其次是将文本信息纳入到我们的方法中，从而利用淘宝 item 中大量的评论信息。

1.2 系统部署

1. 这里我们介绍我们的 graph embedding 方法在淘宝中的实现和部署。我们首先对支撑淘宝的整个推荐平台进行 high-level 的介绍，然后详细说明与我们 embedding 方法相关的模块。

2. 下图给出了淘宝推荐平台的架构。该平台由两个子系统组成：online 和 offline 。

   • 在线子系统主要组件（component）是淘宝个性化平台 （Taobao Personality Platform: TPP）和排序服务平台（Ranking Service Platform: RSP）。典型的工作流程如下图所示：

     • 当用户打开手机淘宝App 时，TPP 抽取用户的最新信息并从离线子系统中检索一组候选 item，然后将候选 item 馈送到 RSP。

     • RSP 使用微调的DNN 模型对候选 item 集合进行排序，并将排序结果返回给 TPP。

     • 用户在淘宝的访问行为被收集并保存为离线子系统的日志数据。

   • 实现和部署 graph embedding 方法的离线子系统的工作流如下所示：

     • 包含用户行为的日志被检索。item graph 是基于用户的行为构建的。在实践中，我们选择最近三个月的日志。

       在生成 session-based 用户行为序列之前，我们会对数据执行反作弊处理（anti-spam processing）。 剩余的日志包含大约 6000 亿条，然后根据前面所述方法构建 item graph 。

     • 为了运行我们的 graph embedding 方法，我们采用了以下的解决方案：

       • 将整个graph 拆分为多个子图，这些子图可以在淘宝的 Open Data Processing Service: ODPS 分布式平台中并行处理。每个子图中大约有 5000 万个节点。

       • 为了在图中生成随机游走序列，我们在 ODPS 中使用我们基于迭代iteration-based 的分布式 graph framework 。随机游走生成的序列总量为 1500 亿左右。

     • 为了实现所提出的 embedding 算法，我们的 XTF 平台使用了 100 个 GPU。在部署的平台上，离线子系统中的所有模块（包括日志检索、反作弊处理、item graph 构建、随机游走序列生成、embedding、item-to-item 相似度计算）都可以在不到六个小时内处理完毕。因此，我们的推荐服务可以在很短的时间内响应用户的最新行为。

   

1.3 实验

1. 这里我们进行了大量的实验来证明我们提出的方法的有效性。

   首先，我们通过链接预测任务对这些方法进行离线评估。然后，我们在手机淘宝 App 上报告在线实验结果。最后，我们展示了一些真实案例，从而在淘宝上深入洞察我们提出的方法。

1.3.1 离线评估

1. 链接预测（Link Prediction）：链接预测任务用于离线实验，因为它是graph 中的一个基础问题fundamental problem 。

   给定一个去掉了某些边的graph，链接预测任务是预测链接的出现。我们随机选择 1/3 的边作为测试集中的 ground truth 并从graph 中移除，剩余的 graph 作为训练集。我们随机选择未链接的节点 pair 对作为负样本并加入到测试集，负样本数量和 ground truth 数量相等。为了评估链接预测的性能，我们选择 AUC 作为评估指标。

2. 数据集：我们选择使用两个数据集进行链接预测任务，它们包含不同类型的辅助信息。

   • Amazon 数据集：来自 Amazon Electronics 的数据集。item graph 通过 “共同购买 co-purchasing “ 关系（在提供的数据中表示为 also_bought）来构建，并使用了三种类型的辅助信息：类目、子类目、品牌。

   • Taobao数据集：来自手机淘宝 App 的数据集。 item graph 根据前述方法来构建。需要注意的是，为了效率和效果，Taobao数据集使用了十二种类型的辅助信息，包括：商家（retailer） 、品牌、购买力水平（purchase level）、年龄、性别、款式（style）等等。根据多年在淘宝的实践经验，这些类型的辅助信息已经被证明是有用的。

   这两个数据集的统计信息如下表所示（#SI 表示辅助信息数量）。我们可以看到这两个数据集的稀疏性都大于 99% 。

   

3. baseline 方法：我们对比了四种方法：BGE、LINE、GES、EGES。

   • LINE 捕获了 graph embedding 中的一阶邻近性和二阶邻近性。我们使用作者提供的实现，并使用一阶邻近性和二阶邻近性运行它，结果分别表示为 LINE(1st) 和 LINE(2nd) 。

   • 我们实现了所提出的 BGE、GES、EGES 等三种方法。

4. 配置：

   • 所有方法的 embedding 维度均设为 160。

   • 对于我们的 BGE/GES/EGES，随机游走的长度为 10，每个节点开始的游走次数为 20，上下文窗口大小为 5 。

5. 实验结果如下表所示，括号中的百分数是相对于 BGE 的提升比例。可以看到：

   • GES 和 EGES 在两个数据集上的 AUC 都优于 BGE、LINE(1st)、LINE(2st)。这证明了所提出方法的有效性。换句话讲，稀疏性问题通过结合辅助信息得到了缓解。

     比较两个数据集上的提升，我们可以看到Taobao 数据集上的提升更为显著。我们将此归因于Taobao 数据集上使用的大量有效且信息丰富的辅助信息。

   • 当在 GES 和 EGES 之间比较，我们可以看到 Amazon 数据集上的性能提升比 Taobao 数据集更大。可能是因为 Taobao 上GES 的表现已经很不错了，即 0.97。因此 EGES 的改善并不突出。而在 Amazon 数据集上，EGES 显著优于 GES。

   基于这些结果，我们可以观察到融合辅助信息对于 graph embedding 非常有用，并且可以通过对各种辅助信息的 embedding 进行加权聚合来进一步提高准确性（accuracy）。

   

1.3.2 在线评估

1. 我们在 A/B test 框架中进行在线实验，实验目标是手机淘宝 App 首页的点击率（ Click-Through-Rate: CTR）。

   我们实现了上面的 graph embedding 方法，然后为每个item 生成一些相似的 item 作为候选推荐。淘宝首页的最终推荐结果由基于dnn 模型的 ranking 引擎生成。在实验中，我们在 ranking 阶段使用相同的方法对候选 item 进行排序。如前所述，相似item 的质量直接影响了推荐结果。因此，推荐性能（即CTR）可以代表不同方法在 matching 阶段的有效性。

   我们将这四种方法部署在一个 A/B test 框架中，2017 年 11 月连续7 天的实验结果如下图所示。其中，Base 代表一种 item-based CF 方法，在部署 graph embedding 方法之前已经在淘宝内部广泛使用。Base 方法根据 item 共现（ co-occurrence）和用户投票权重计算两个item 之间的相似度，并且相似度函数经过精心调优从而适合淘宝的业务。

   可以看到：

   • EGES 和 GES 在 CTR 方面始终优于 BGE 和 Base，这证明了在 graph embedding 中融合辅助信息的有效性。

   • 此外，Base 的 CTR 优于 BGE。这意味着经过精心调优的 CF-based 方法可以击败简单的 embedding 方法，因为在Base 方法中已经利用了大量人工设计的启发式策略。

   • EGES 始终优于 GES，这和离线实验结果相一致。这进一步证明了辅助信息的加权聚合优于平均聚合。

   

1.3.3 案例研究

1. 这里我们展示了淘宝中的一些真实案例来说明我们方法的有效性。这些案例从三个方面来研究：EGES embedding 的可视化、冷启动item、EGES 中的加权权重。

2. embedding 可视化：我们通过 tensorflow 提供的可视化工具，将 EGES 学到的 item embedding 可视化，结果如下图所示。下图为一组随机选择的运动鞋的embedding 的可视化，item embedding 通过 PCA 投影到二维平面中，其中不同颜色代表不同的类目。

   • 从图 (a) 中，我们可以看到不同类目的鞋子在不同的 cluster 中。这里一种颜色代表一类鞋子，例如羽毛球鞋、乒乓球鞋、足球鞋。

     这证明了融合辅助信息来学习 emebdding 的有效性，即具有相似辅助信息的 item 应该在 embedding 空间中更接近。

   • 从图 (b) 中，我们进一步分析了羽毛球鞋、乒乓球鞋、足球鞋三种鞋子的 embedding。我们观察到一个有趣的现象：羽毛球鞋和乒乓球鞋的 embedding 距离更接近、和足球鞋的 embedding 距离更远。

     这一现象可以解释为：在中国，喜欢乒乓球的人和喜欢羽毛球的人有很多重叠。然而喜欢足球的人和喜欢室内运动（如乒乓球、羽毛球）的人，有很大的不同。从这个意义上讲，向看过乒乓球鞋的人推荐羽毛球鞋，要比推荐足球鞋要好得多。

   

3. 冷启动 item：对于淘宝中的新item，无法从 item graph 中学习到 embedding，并且之前CF-based 的方法也无法处理冷启动item。因此，我们利用新item 的辅助信息的平均 embedding 来表示一个冷启动 item。然后我们根据item embedding 的内积从所有 item 中检索和冷启动 item 最相似的 item。

   结果如下图所示，我们给出了冷启动item 的 top 4 相似item。在图中，我们为每个相似 item 标注了与冷启动item 相关的辅助信息的类型，其中 cat 意思是 category

   可以看到：

   • 尽管缺少用户对冷启动 item 的行为，但是可以利用不同的辅助信息来有效地学习它们embedding（就 top 相似 item 的质量而言）。

   • item 的门店shop 对于衡量两个item 的相似性非常有用，这也和下面介绍的辅助信息的权重保持一致。

   

4. 辅助信息权重：我们将item 的不同类型辅助信息的权重可视化。我们选择了不同类目的 8 个item，并从学到的权重矩阵 $\mathbf{A}$$\mathbf A$ 中提取与这些 item 相关的所有辅助信息的权重。结果如下图所示，其中每一行记录一个 item 的权重结果。

   有几点值得注意：

   • 不同 item 的权重分布不同，这和我们的假设相一致，即不同的辅助信息对最终 representation 的贡献不同。

   • 在所有 item 中，代表 item 本身 embedding 的 "Item" 权重始终大于所有其它辅助信息的权重。这证实了一种直觉，即 item embedding 本身仍然是用户行为的主要来源，而辅助信息为推断用户行为提供了额外的提示。

   • 除了 "Item" 之外，"Shop" 的权重始终大于其它辅助信息的权重。这和淘宝中的用户行为一致，即用户倾向于在同一家店铺购买item，这是为了便利性（convenience）和更低的价格（即店铺的折扣）。